import java.util.ArrayList;
import java.util.List;

public class Kombinatsioonid {
	public static void main(String[] args) {

		int mitukuuli = 5, mituvalitud = 3;

		List<Integer> algseis = new ArrayList<Integer>();
		for (int i = 0; i < mitukuuli; i++)
			algseis.add(new Integer(0));

		List<List<Integer>> kombinatsioonid = kombi(algseis, mituvalitud);

		for (int i = 0; i < kombinatsioonid.size(); i++) {
			System.out.println(kombinatsioonid.get(i));
		}
		System.out.println("Kombinatsioone: " + kombinatsioonid.size());
	}

	public static List<List<Integer>> kombi(List<Integer> algseis,
			int mitmeKaupa) {
		int yhtesid_l6pus, suurus = algseis.size();
		for (int i = 0; i < mitmeKaupa; i++) {
			algseis.add(0, new Integer(1));
			algseis.remove(suurus - 1);
		}
		List<List<Integer>> kombinatsioonid = new ArrayList<List<Integer>>();
		kombinatsioonid.add(koopia(algseis));

		do {
			int nulle_l6pus = 0;
			for (int i = suurus - 1; i > 0 && algseis.get(i) == 0; i--, nulle_l6pus++) ;

			for (int i = suurus - nulle_l6pus - 1; nulle_l6pus > 0; nulle_l6pus--) {
				algseis.remove(suurus - 1);
				algseis.add(i, new Integer(0)); // liiguta viimast 1 l6ppu
				kombinatsioonid.add(koopia(algseis));
			}

			yhtesid_l6pus = 0;
			for (int i = suurus - 1; algseis.get(i) == 1 && i > 0; i--, yhtesid_l6pus++) ;

			for (int i = suurus - 1; i > 0 && yhtesid_l6pus > 0; i--) {
				if (algseis.get(i - 1).intValue() == 1 && algseis.get(i).intValue() == 0) {
					for (int k = 0; k < yhtesid_l6pus; k++) {
						algseis.add(i - 1, new Integer(1)); // lisa 1 niipalju kui on l6pus
						algseis.remove(suurus - 1);
					}
					algseis.remove(suurus - 1);
					algseis.add(i - 1, new Integer(0)); // nihuta paremale
					break;
				}
			}

			if (yhtesid_l6pus != mitmeKaupa)   // et l6pus kordust poleks, kui on 1 kaupa n-st v6i n kaupa n-st
				kombinatsioonid.add(koopia(algseis));

		} while (yhtesid_l6pus != mitmeKaupa);

		return kombinatsioonid;
	}

	public static List<Integer> koopia(List<Integer> massiiv) {
		List<Integer> massiiv_copy = new ArrayList<Integer>();
		massiiv_copy.addAll(massiiv);
		return massiiv_copy;
	}

}
